This invention relates to a k-nearest neighbor search technique for strictly searching arbitrary multidimensional points for k nearest points at high speed, and more particularly, to a technique for searching for points in a two-dimensional or three-dimensional space assuming map information management.
A database management system that has a spatial search function has been developed for the purpose of map information management. This database management system is referred to as a spatial database management system. The spatial database management system enables management of graphic elements such as points, lines or surfaces of objects, and attribute elements such as characters or numerical values indicating contents of the objects. The spatial search function realizes range search for obtaining objects included or in contact with an arbitrary range. To achieve a high speed of range search, a spatial index technique such as quadtree, grid file, or R-tree has been proposed. The spatial index technique divides a spatial region according to arrangement and distribution of objects in the space area.
The spatial database management system has conventionally been developed for enterprise applications. Recently, however, a spatial database management system has been developed also for application to an embedded device. The embedded device that needs the spatial database is a device such as a car navigation device or a personal navigation device (PND) for managing map information. The car navigation device has a function of searching a spatial database for points such as restaurants or parking lots near a given point such as a current location or a destination designated by a user. For that purpose, k-nearest neighbor search for obtaining a number k (hereinafter referred to as a query number) of nearest points to the user-designated point (hereinafter referred to as a query point) from the spatial database has been known.
The k-nearest neighbor search in the conventional spatial database management system is realized by using range search. According to the conventional k-nearest neighbor search, first, a search range of an arbitrary size around a query point is set. If the number of points included in the search range exceeds the query number, distances between the query point and the respective points are calculated. The points are sorted in order of increasing distances, and k nearest points are obtained as the search result. On the other hand, if the number of points included in the search range is less than the query number, until the number exceeds the query number, a larger search range is set to repeat the range search. For example, a method that uses range search based on a grid file (JP 2003-242151 A) and a method that uses range search based on quadtree (U.S. Pat. No. 6,879,980) have been known.